package linear.stack.impl;

import linear.stack.Stack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 栈
 * @author caasi
 * @since 2022-01-19 09:09:33
 */
public class StackImpl<E> implements Stack<E> {

    private static final Map<String, Integer> priorityMap = new HashMap<>();

    private Node<E> top;

    private int size;

    public StackImpl() {
        this.size = 0;
    }

    static {
        priorityMap.put("+", 1);
        priorityMap.put("-", 1);
        priorityMap.put("*", 2);
        priorityMap.put("/", 2);
        priorityMap.put("(", 3);
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public E pop() {
        if (top == null)
            return null;
        E v = top.value;
        top = top.next;
        size--;
        return v;
    }

    @Override
    public void push(E e) {
        Node<E> node = new Node<>(e, top);
        top = node;
        size++;
    }

    @Override
    public E peek() {
        return top == null ? null : top.value;
    }

    @Override
    public Iterator<E> iterator() {
        return new StackIterator();
    }

    //括号匹配问题
    @Override
    public boolean roundBracketsQuestion(String s) {
        Stack<Character> stack = new StackImpl<>();
        if (s == null || s.trim().length() == 0)
            return true;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            //如果是左括号直接入栈
            if (c.equals('('))
                stack.push(c);
            //如果是右括号则出栈，并判断出栈的元素是否是null，为null直接返回false，不为null则继续循环
            if (c.equals(')')) {
                Character pop = stack.pop();
                if (pop == null)
                    return false;
            }
        }
        //结束后检查栈中是否还有元素
        int size = stack.size();
        return size == 0;
    }

    //计算表达式：中缀表达式
    @Override
    public String calculateNotation(String[] notation) {
        if (notation == null || notation.length == 0)
            throw new IllegalArgumentException("表达式不能为空");
        return calculateReversePolishNotation(genReversePolishNotation(notation));
    }

    //将中缀表达式转换为逆波兰表达式
    private String[] genReversePolishNotation(String[] notation) {
        StringBuffer sb = new StringBuffer();
        Stack<String> stack = new StackImpl<>();
        for (int i = 0; i < notation.length; i++) {
            String s = notation[i];
            if (!isOperator(s))
                //如果是操作数直接输出
                sb.append(s).append(",");
            else {
                //如果是操作符需要根据情况而定
                String top = stack.peek();
                if (s.equals(")")) {
                    //1.当前操作符为“)”，则一直弹出栈内操作符直到栈顶为“(”
                    while (!top.equals("(")) {
                        sb.append(stack.pop()).append(",");
                        top = stack.peek();
                    }
                    //然后弹出“(”
                    stack.pop();
                } else {
                    //2.比较当前操作符和栈顶的优先级，如果高于栈顶的优先级则入栈，如果低于或等于，则弹出元素，直到栈顶元素为“(”或优先级高于栈顶或栈为null
                    while (top != null && comparePriority(top, s) <= 0 && !top.equals("(")) {
                        sb.append(stack.pop()).append(",");
                        top = stack.peek();
                    }
                    stack.push(s);
                }
            }
        }
        //将栈中剩余的操作符依次弹出
        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(",");
        }
        String result = sb.toString();
        return result.substring(0, result.lastIndexOf(",")).split(",");
    }

    //比较栈顶操作符和当前操作符的优先级
    private Integer comparePriority(String top, String operator) {
        return priorityMap.get(operator) - priorityMap.get(top);
    }

    //计算逆波兰表达式
    private String calculateReversePolishNotation(String[] notation) {
        Stack<String> stack = new StackImpl<>();
        for (int i = 0; i < notation.length; i++) {
            String s = notation[i];
            if (!isOperator(s))
                //操作数直接入栈
                stack.push(s);
            else {
                String rightOperand = stack.pop();
                String leftOperand = stack.pop();
                String result = calculate(leftOperand, rightOperand, s);
                //入栈
                stack.push(result);
            }
        }
        return stack.pop();
    }

    //计算
    private String calculate(String left, String right, String operator) {
        String result = "0";
        switch (operator) {
            case "+":
                result = Double.valueOf(left) + Double.valueOf(right) + "";
                break;
            case "-":
                result = Double.valueOf(left) - Double.valueOf(right) + "";
                break;
            case "*":
                result = Double.valueOf(left) * Double.valueOf(right) + "";
                break;
            case "/":
                result = Double.valueOf(left) / Double.valueOf(right) + "";
                break;
        }
        return result;
    }

    //判断是否是操作符
    private boolean isOperator(String s) {
        return "+-*/()".indexOf(s) > -1;
    }

    //迭代器
    private class StackIterator implements Iterator<E> {

        private Node<E> begin;

        public StackIterator() {
            begin = top;
        }

        @Override
        public boolean hasNext() {
            return begin != null;
        }

        @Override
        public E next() {
            E v = begin.value;
            begin = begin.next;
            return v;
        }
    }

    private class Node<E> {

        private Node<E> next;

        private E value;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }

    }

}
